Archive for January 2009


Generic blog entry

January 23rd, 2009 — 11:17 am

I don’t have a special theme for today, nor am I feeling very organized, so here are some thoughts in no particular order.

  • LeaderShape was very, very fun.  I highly reccomend it
  • I spread myself too thin
  • I need to vacuum the carpet
  • Reading is terribly relaxing
  • “The King of the Golden Hall” is a fantastic song (from The Two Towers soundtrack)
  • I need to change my lifestyle for good.  It’s no good being a dreamer and not a doer.
  • I want to end this with a poem by Mary Oliver

How everything adores being alive

What

if you were

a beetle,

and a soft wind

and a certain allowance of time

had summoned you

out of your wrappings,

and there you were,

so many legs,

hardening,

maybe even

more than one pair of eyes

and the whole world

in front of you?

And what if you had wings

and flew

into the garden,

then fell

into the up-tipped

face

of a white flower,

and what if you had

a sort of mouth,

a lip,

to place close

to the skim

of honey

that kept offering itself -

what would you think then

of the world

as, night and day,

you were kept there -

oh happy prisoner -

sighing, humming,

roaming

that deep cup?

3 comments » | Uncategorized

Outward bound!

January 16th, 2009 — 12:55 pm

I’m going to be out until Wednesday, as I am leaving for the 2009 installment of LeaderShape (!).  I’m awfully excited - I’ve heard great things about the program, and can’t wait to see what the hype’s about.

1 comment » | Uncategorized

TOC 3 - Regular Operations, Pumping Lemma

January 16th, 2009 — 12:15 pm

Today we will discuss Regular Expressions (which you might have heard of if you’re a programmer), their relation to Regular Languages, and the Pumping Lemma.  This will conclude our discussion of Automata and we can then move onto more complex and interesting models of Computation.

Regular Languages

Def: A language is a regular language if there exists some finite automata that recognizes it.

Easy enough, no?  That means that all the languages that we were working with in the last two entries were actually Regular Languages.

You’ve probably heard of Regular Expressions if you’re a programmer.  They’re a great way of working with text, and save a lot of time.  In our context, we will consider the effects of three specific Regular Operations on Languages (sets of strings of words).  The operations are:

  • Union.  A \cup B = \{ x | x \in A or x \in B\}
  • Concatenation.  A \circ B = \{ xy | x \in A and y \in B \}
  • Star.  A^* = \{ x_1... x_k | k \geq 0, x_i \in A \} .  Note here that the condition k \geq 0 means that k could equal zero.

Pretty simple, right?  Well, it turns out that the Regular Languages have an interesting property: they are closed under Regular Operations.  That means that, if you had regular languages A and B, and did some combination of Regular Operations on them, the result would be a langauge C that you 100% sure could find a Finite Automata for.  Let’s go through these one by one.

Union.  We wish to show that, given regular languages A and B the union of them is also regular.  Because they are regular, there exists DFAs M_A and M_B that recognize them respectively.  Consider the sets of states of these machines, Q_A and Q_B.  We construct a machine with states Q' = Q_A \times Q_B.  The behavior of this should be natural, then.  The start state will be Q'_0 = (q_{A0}, q_{B0}), the transition function is defined \delta' (q_A, q_B) = (\delta _A (q_A) , \delta _B (q_B)).  The accept states are the set F' = (q_A, q_B), where at least one of q_A or q_B were accept states for their respective machines.  Given a string then, this machine will “simulate” both M_A and M_B on the word, and accept if one of those accepts.

Concatenation.  This is easy with the use of nondeterminism.  Given machines M_A and M_B, we construct an NDA M' that accepts A \circ B.  The construction of M' is easier to visualize with a graphical depiction, so we will forgo the formalism of the earlier proofs.  Basically, take M_A and M_B, and have nondeterministic \epsilon-transitions from the accept states of M_A to the start state of M_B.  That way, each time we reach a word in A, we nondeterministically branch to check if either the rest of the string is in B, or if we should go on further.  Moreover, the only accept states are the accept states of M_B.  It is noted that the original state transitions of M_A and M_B are conserved here as well.

Star Operation.  We use nondeterminism here as well.  Start with the deterministic machine M_A that accepts the language.  We first make it a nondeterministic machine, then add a new start state that points to the start state of the former machine (denoted q_{A0}).  The new start state is an accept state to account for the fact that the star operation includes the empty string.  Also, the start state has an \epsilon-transition to q_{A0}, so that we can effectively simulate M_A on the input.  We keep the accept states of M_A, and add \epsilon-transitions to q_{A0} (can you see why?).

The three constructions above show the closure of the regular operations.  In addition, the proofs should show you a little about how nice nondeterminism can be when trying to solve a problem.  Anyway, now that we know more about regular languages, we can state the Pumping Lemma, which is used to show when a language is nonregular.

Pumping Lemma: If A is a regular language, there exists p a positive integer where for any string w \in A of length greater than p, w may be written as the concatenation of strings wxy where:

  1. For any i \geq 0, xy^iz \in A
  2. |y| > 0
  3. |xy| < p

I’m not going to prove this lemma, but it has to do with the finite number of states that Automata have.  If you want to try that for an exercise, it shouldn’t be difficult - just make sure you’re being rigorous.  Also, I would like to emphasize that the number p is a fixed number specific to the language.

Anyway!  That’s all I really want to say about finite automata.  We’ll start learning about everyone’s favorite model of computation - the Turing Machine - next entry.  But for now, why don’t you try these problems to check your understanding of the bit we just learned?

- Show that the following language is not regular:  \{ 0^n1^m0^n | m, n \geq 0 \}

- Let C_n = \{x | x a binary number that is a multiple of n \}.  Show that for each n \geq 1,  the language is regular.

Comment » | Academia, TOC

“Jack of all trades, master of none”

January 13th, 2009 — 01:24 pm

… was something I read today, and wanted to share.

I’m sorry that I haven’t been keeping up with my entries, all five of my readers.  I’ll try to give a decent update of things that have happened (snowboarding, the UROP situation, and going “waka waka waka”).  And maybe even another TOC entry (if completed, it will be about Regular Expressions, Languages, and the Pumping Lemma) that I’ve been meaning to write for a while.

If I don’t update soon though, it will be a while before I do, because I’m leaving for LeaderShape on Friday, and will be gone to the wilderness with other future leaders, staving off bears and eating cup noodles.

Toodle doo!

1 comment » | Uncategorized

The things we do.

January 3rd, 2009 — 05:22 pm

I have been thinking a lot over the past few days about my habits and the activities that I choose to fill my day with.  I must admit- a great fraction of my days at home are spent without activity.  I go online, chat up some friends, check my email and RSS, and then let my brain rot for a few hours on reddit, an investment which will ultimately bring me a few cheap laughs in the comments section.  In fact, when I consider the sheer amount of time I spend on that site, it’s probably one of the worst things I could be doing with my day.  Heck, at least starcraft gets me some sense of multitasking and reflexes.  Reddit, on the other hand, offers me nearly nothing.

So what is it that I do love doing?  I asked my brother this yesterday.  He’s 9, turning 10 in a few days, and spends an obscene amount of time playing Maple Story and watching the Disney Channel.  But we both came up with the conclusion that these things that we spent so much of our days doing… we didn’t really enjoy.

So what is it that I really love to do?  It’s not that difficult, actually!  Playing games in the outdoors.  Going for a nice bike ride, feeling the wind in my face.  I love taking slow walks outside, and singing little tunes in the hall, cooking a nice wok full of fried rice.  I love playing tennis, reading books by lamplight, and doing handstands and toppling over.  Laughing stupidly for no reason at all.  Saying “hi” to strangers.  These things are so easy to do, and they’re so rewarding.  So why don’t I do them more often?

This entry is actually an outline for a New Year Resolution, both for me and the rest of you.  Why don’t we figure out what we actually, really love doing in this world, with ourselves, to run with them and embrace them. After all, why not?

It’s been a wonderful 2008, and I have only hope for ‘09.

4 comments » | Uncategorized